// 利用切分性质就可以求出图的最小生成树

/**
 * 算法基本思路：
 *      1：选择一个顶点作为起点，加入切分集合U中
 *      2：获取该切分集中代价最小的一条边，将边的V-U顶点加入U中
 *      3：更新切分集
 *      重复以上2，3步骤，直到所有的顶点都加入了切分集合U当中
 */



 /**
  * 以下算法针对的是 邻接矩阵的存贮方式
  * 为实现prim算法需要设置一个辅助数组closedge，用于记录从U（切分集合）到V-U（非切分集合）具有最小代价的边
  * 数组中的数据元素包含两个域：lowcost（权值），vex（依附在U中的顶点）
  */

  class EdgeNode{
      constructor(lowcost, vex) {
          this.lowcost = lowcost
          this.vex = vex
      }
  }

 function prim(gn) {
     let v, i, j, k, vtxnum = gn.length, closedge = []
     // 根据邻接矩阵的值对辅助数组进行初始化
     for (v = 1; i < vtxnum; v++) {
        const node = new EdgeNode()
        closedge[v] = node
        closedge[v].vex = 0
        closedge[v].lowcost = gn[0][v]
    }
    // 从gn下标为0的位置出发
    closedge[0].vex = 0
    closedge[0].lowcost = 0 // lowcost = 0 表示该顶点加入了切分集合当中

    for (i = 1; i < vtxnum; i++) {
        k = minmum(closedge) // 在切分集合中寻找具有最小权重的边  
        console.log(closedge[k].vex, k) // 输出最小生成树的边
        closedge[k].lowcost = 0 // 加入U中
        // 加入新的节点后切分集和发生了变化，需要更新 closedge
        for (v = 1; v < vtxnum; v++) {
            if (gn[k][v] < closedge[v]) { // 节点最小代价的更新
                closedge[v].vex = k
                closedge[v].lowcost = g[k][v]
            }
        }
    }

    // 在辅助数组中寻找最小代价的节点
    
    function minmum(closedge) {
        let k, min = 100000, h = 1
        for (k = 1; k < vtxnum; k++) {
            // 在切分集中寻找最小的边
            if (closedge[k].lowcost != 0 && closedge[k].lowcost < min) {
                min = closedge[k].lowcost
                h = k
            }
        }
        return h
    }
 }